package leetcodecompetition.S100;

import org.junit.jupiter.api.Test;
import tool.s;

import java.util.Arrays;

public class T6325 {
    public long repairCars(int[] ranks, int cars) {
        Arrays.sort(ranks);
        int len = ranks.length;
        int[] nums = new int[len];
        long[] l = new long[len];
        nums[0] = cars;
        l[0] = ranks[0] * nums[0] * nums[0];
        while (true) {
            int max = 0;
            int min = 0;
            long maxindex = l[0];
            long minindex = l[0];
            for (int i = 1; i < len; i++) {
                if (l[i] > maxindex) {
                    max = i;
                    maxindex = l[i];
                }
                if (l[i] < minindex) {
                    min = i;
                    minindex = l[i];
                }
            }
            long max1 = l[max] - ranks[max]*(2 * nums[max] - 1);
            long min1 = l[min] + ranks[min]*(2 * nums[min] + 1);
            if (min1 < maxindex && max != min) {
                nums[max]--;
                l[max]=max1;
                nums[min]++;
                l[min]=min1;
            } else {
                return maxindex;
            }
        }
    }

    @Test
    public void test() {
        int[] rank = {4, 2, 3, 1};
        System.out.println(repairCars(rank, 10));

    }
}
